
/*
 * Copyright (C) 2008-2009 Archie L. Cobbs. All rights reserved.
 *
 * $Id: PackedLong.java 379 2010-03-11 21:41:43Z archie.cobbs $
 */

package org.dellroad.sidekar.util;

import java.io.EOFException;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;

/**
 * An improved version of Berkeley DB's {@link com.sleepycat.util.PackedInteger} class that packs values in such
 * a way that their order is preserved when compared using the default binary unsigned lexical ordering.
 *
 * @see <a href="http://forums.oracle.com/forums/thread.jspa?messageID=4126254">Berkeley DB Java Edition forum posting</a>
 */
public final class PackedLong {

    /**
     * Maximum possible length of an encoded value.
     */
    public static final int MAX_ENCODED_LENGTH = 9;

    /**
     * Minimum value for the first byte of a single byte encoded value. Lower values indicate a multiple byte encoded
     * negative value.
     */
    public static final int MIN_SINGLE_BYTE_ENCODED = 0x08;        // values 0x00 ... 0x07 prefix negative values

    /**
     * Maximum value for the first byte of a single byte encoded value. Higher values indicate a multiple byte encoded
     * positive value.
     */
    public static final int MAX_SINGLE_BYTE_ENCODED = 0xf7;        // values 0xf8 ... 0xff prefix positive values

    /**
     * Adjustment applied to single byte encoded values before encoding.
     */
    public static final int ZERO_ADJUST = 127;                     // single byte value that represents zero

    /**
     * Minimum value that can be encoded as a single byte.
     */
    public static final int MIN_SINGLE_BYTE_VALUE = MIN_SINGLE_BYTE_ENCODED - ZERO_ADJUST;          // -119

    /**
     * Maximum value that can be encoded as a single byte.
     */
    public static final int MAX_SINGLE_BYTE_VALUE = MAX_SINGLE_BYTE_ENCODED - ZERO_ADJUST;          // 120

    /**
     * Adjustment applied to multiple byte encoded negative values before encoding.
     */
    public static final int NEGATIVE_ADJUST = -MIN_SINGLE_BYTE_VALUE;                               // 119

    /**
     * Adjustment applied to multiple byte encoded positive values before encoding.
     */
    public static final int POSITIVE_ADJUST = -(MAX_SINGLE_BYTE_VALUE + 1);                         // -121

    // Cutoff values at which the encoded length changes (this field is package private for testing purposes)
    static final long[] CUTOFF_VALUES = new long[] {
        0xff00000000000000L - NEGATIVE_ADJUST,      // [ 0] requires 8 bytes
        0xffff000000000000L - NEGATIVE_ADJUST,      // [ 1] requires 7 bytes
        0xffffff0000000000L - NEGATIVE_ADJUST,      // [ 2] requires 6 bytes
        0xffffffff00000000L - NEGATIVE_ADJUST,      // [ 3] requires 5 bytes
        0xffffffffff000000L - NEGATIVE_ADJUST,      // [ 4] requires 4 bytes
        0xffffffffffff0000L - NEGATIVE_ADJUST,      // [ 5] requires 3 bytes
        0xffffffffffffff00L - NEGATIVE_ADJUST,      // [ 6] requires 2 bytes
        MIN_SINGLE_BYTE_VALUE,                      // [ 7] requires 1 byte
        MAX_SINGLE_BYTE_VALUE + 1,                  // [ 8] requires 2 bytes
        0x0000000000000100L - POSITIVE_ADJUST,      // [ 9] requires 3 bytes
        0x0000000000010000L - POSITIVE_ADJUST,      // [10] requires 4 bytes
        0x0000000001000000L - POSITIVE_ADJUST,      // [11] requires 5 bytes
        0x0000000100000000L - POSITIVE_ADJUST,      // [12] requires 6 bytes
        0x0000010000000000L - POSITIVE_ADJUST,      // [13] requires 7 bytes
        0x0001000000000000L - POSITIVE_ADJUST,      // [14] requires 8 bytes
        0x0100000000000000L - POSITIVE_ADJUST,      // [15] requires 9 bytes
    };

    private PackedLong() {
    }

    /**
     * Write the encoded value to the output.
     *
     * @param output destination for the encoded value
     * @param value value to encode
     */
    public static void write(OutputStream output, long value) throws IOException {
        output.write(PackedLong.encode(value));
    }

    /**
     * Read and decode a value from the input.
     *
     * @param input input holding an encoded value
     * @return the decoded value
     */
    public static long read(InputStream input) throws IOException {
        int first = input.read();
        if (first == -1)
            throw new EOFException();
        int len = PackedLong.getReadLength(first);
        byte[] buf = new byte[len];
        buf[0] = (byte)first;
        int total = 1;
        while (total < len) {
            int r = input.read(buf, total, len - total);
            if (r == -1)
                throw new EOFException();
            total += r;
        }
        return PackedLong.decode(buf, 0);
    }

    /**
     * Determine the length (in bytes) of an encoded value based on the first byte.
     *
     * @param first first byte of encoded value
     * @return the length of the encoded value (including the first byte)
     * @throws ArrayIndexOutOfBoundsException if {@code off} is not a valid offset in {@code buf}
     */
    public static int getReadLength(int first) {
        int prefix = first & 0xff;
        if (prefix < MIN_SINGLE_BYTE_ENCODED)
            return 1 + MIN_SINGLE_BYTE_ENCODED - prefix;
        if (prefix > MAX_SINGLE_BYTE_ENCODED)
            return 1 + prefix - MAX_SINGLE_BYTE_ENCODED;
        return 1;
    }

    /**
     * Determine the length (in bytes) of the encoded value.
     *
     * @return the length of the encoded value, a value between one and {@link #MAX_ENCODED_LENGTH}
     */
    public static int getWriteLength(long value) {
        int index = Arrays.binarySearch(CUTOFF_VALUES, value);
        if (index < 0)
            index = ~index - 1;
        return index < 8 ? 8 - index : index - 6;
    }

    /**
     * Encode the given value into a new buffer.
     *
     * @param value value to encode
     * @return byte array containing the encoded value
     */
    public static byte[] encode(long value) {
        byte[] buf = new byte[MAX_ENCODED_LENGTH];
        int len = encode(value, buf, 0);
        if (len != MAX_ENCODED_LENGTH) {
            byte[] newbuf = new byte[len];
            System.arraycopy(buf, 0, newbuf, 0, len);
            buf = newbuf;
        }
        return buf;
    }

    /**
     * Encode the given value and write the encoded bytes into the given buffer.
     *
     * @param value value to encode
     * @param buf output buffer
     * @param off starting offset into output buffer
     * @return the number of encoded bytes written
     * @throws ArrayIndexOutOfBoundsException if {@code off} is negative or the encoded value exceeds the given buffer
     */
    public static int encode(long value, byte[] buf, int off) {
        int len = 1;
        if (value < MIN_SINGLE_BYTE_VALUE) {
            value += NEGATIVE_ADJUST;
            long mask = 0x00ffffffffffffffL;
            for (int shift = 56; shift != 0; shift -= 8) {
                if ((value | mask) != ~0L)
                    buf[off + len++] = (byte)(value >> shift);
                mask >>= 8;
            }
            buf[off] = (byte)(MIN_SINGLE_BYTE_ENCODED - len);
        } else if (value > MAX_SINGLE_BYTE_VALUE) {
            value += POSITIVE_ADJUST;
            long mask = 0xff00000000000000L;
            for (int shift = 56; shift != 0; shift -= 8) {
                if ((value & mask) != 0L)
                    buf[off + len++] = (byte)(value >> shift);
                mask >>= 8;
            }
            buf[off] = (byte)(MAX_SINGLE_BYTE_ENCODED + len);
        } else {
            buf[off] = (byte)(value + ZERO_ADJUST);
            return 1;
        }
        buf[off + len++] = (byte)value;
        return len;
    }

    /**
     * Decode a value from the given buffer.
     *
     * @param buf buffer containing an encoded value
     * @param off starting offset of the encoded value in {@code buf}
     * @return the decoded value
     * @throws ArrayIndexOutOfBoundsException if {@code off} is negative or the encoded value is truncated
     * @see #getReadLength
     */
    public static long decode(byte[] buf, int off) {
        int first = buf[off++] & 0xff;
        if (first < MIN_SINGLE_BYTE_ENCODED) {
            long value = ~0L;
            while (first++ < MIN_SINGLE_BYTE_ENCODED)
                value = (value << 8) | (buf[off++] & 0xff);
            return value - NEGATIVE_ADJUST;
        }
        if (first > MAX_SINGLE_BYTE_ENCODED) {
            long value = 0L;
            while (first-- > MAX_SINGLE_BYTE_ENCODED)
                value = (value << 8) | (buf[off++] & 0xff);
            return value - POSITIVE_ADJUST;
        }
        return (byte)(first - ZERO_ADJUST);
    }
}

